/**
 * 
 */
package leetCode;

/**
 * @author zhong
 *
 */
public class SuperEggDrop {

	int helper(int K, int times) {
		if (K == 1) {
			return times;
		}

		if (K >= times) {
			return (int) Math.pow(2, times) - 1;
		}

		return helper(K, times - 1) + helper(K - 1, times - 1) + 1;
	}

	public int superEggDrop(int K, int N) {
		int times = 1;
		while (helper(K, times) < N) {
			++times;
		}
		return times;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int K = 100, N = 10000;
		System.out.println(new SuperEggDrop().superEggDrop(K, N));
	}

}
